Meeting KAUST

About Euclidean graphs

The definition of Euclidean graphs given by Anderes et al. (2020) is the following:

The only condition is given by point c), the distance consistency. This condition resembles a triangular inequality (for this reason Euclidean?). It seems that a necessary (and maybe sufficient) condition to satisfy this property is the following: “if two vertices are connected by an edge, this must be the shortest path (under any chosen metric)”.

Therefore, it looks like we can transform a non-Euclidean graph by breaking any edge connecting two nodes, which does not represented the shortest path between the two, adding a new node and dividing the edge in two “sub”-edges.

For instance, in the cycle example the distance consistency implies that:

\[ \overline{e}_0 - \underline{e}_0 \leq \sum_{\mathcal{E}\ni e\neq e_0} (\overline{e}-\underline{e}), \]

which means that any edge cannot span more than half of the circumference. But if any edge violates this requirement, one can just break down the edge by adding a new node and having the condition satisfied.

1. Is there any fallacy in this reasoning?
2. If not, what then is the “true” meaning (and the effect) of having a 2-degree node in the network? We can add and remove them, and obtain Euclidean and non-Euclidean graphs.

Image from Anderes et al. (2020)

Image from Porcu et al. (2023)

Sensitivity analysis

We can perhaps reason about two directions of sensitivity analysis: model-related sensitivity or signal-related sensitivity.

We can refer to model-related sensitivity as the one regarding the robustness of a given model. For instance: parameter estimates, prediction accuracy, uncertainty calibration, etc..

Meanwhile, we can refer to signal-related sensitivity as the robustness of empirical-based estimates regarding functions defined on graphs, such as empirical variogram in spatial contexts.

Possibly for both types of sensitivities, we can consider two perturbation scenarios:

1. Perturbation of the observed values in some point, given the network. Ideally, we would like to see and learn patterns for the robustness of the model estimates against some topological features of the network
2. Perturbation of the network, given the observed values. It is perhaps meaningful if we observe the process only on the verteces and, e.g., we consider removing or adding edges.

For the simulations we rely on the R-package MetricGraph. The package allows us to manipulate networks, simulate data, and estimate some models. In particular, all simulated data comes from the Whittle-Matern process.

Model-related sensitivity

At this stage, the general experiment is given by the following procedure:

1. Define a (Euclidean) metric graph.
2. Simulate data from the WM model, fixing the hyperparameters. We can consider different data locations (we always include the network verteces).
3. Consider different level h of perturbations of the data at the verteces.
4. Fit the WM model and the isoCov model, and look at the parameter estimates.

TODO In general, we can simulate the data also from the isoCov process by defining the locations, computing the pairwise resistance distances, and sample the associated multivariate Gaussian. This sounds more reasonable as in this way we can fairly compare the estimates to the true parameter values for both processes.

The Whittle-Matern field model (Bolin et al., 2023)

The WM model is defined through a SPDE on the graph (with proper notions of differential operators and boundary conditions on the graph): \[ (\kappa^2 - \Delta)^{\alpha/2}\tau u = W, \] where \(W\) is the white noise process. Parameter \(\tau^2\) is related to the inverse of the variance, \(\kappa\) is related to the length-scale of the model, and \(\alpha\) to the smoothness. The above equation relates to the classical Matern covariance as follows: \[ r(d)=\frac{\Gamma(\nu)}{\tau^2\Gamma(\nu+1/2)\sqrt{4\pi}\kappa^{2\nu}}(\kappa d)^\nu \mathcal{K}_\nu(\kappa d), \] considering \(\alpha = \nu + 1/2\). The R package has two different parametrizations: \((\nu,\sigma,\rho)\) and \((\alpha,\tau,\kappa)\), where \(\rho\) is named range and it is the practical correlation range (i.e, correlation less than 0.1 for \(d>\rho\)). The relation between the two parametrizations is the following:

\[ \begin{cases} \alpha = \nu + 1/2 \\ \rho = \sqrt{8\nu}/\kappa \\ \sigma^2 = \frac{\Gamma(\nu)}{\tau^2\Gamma(\nu+1/2)\sqrt{4\pi}\kappa^{2\nu}} \end{cases} \]

The isotropic (exponential) covariance model (Anderes et al, 2020)

The covariance function is the following: \[ r(d_R) = \tau^2 \text{exp}(- \kappa d_R), \] where \(d_R\) is the resistance metric on the graph. The MetricGraph parameterization is given by \((\tau,\kappa)\), where this time \(\tau^2\) is proportional to the marginal variance, rather than the precision (confusing notation).

Simulations

We consider the following examples of networks. Networks Complete (all 1), Star, and Random (all1) have all edges of unitary length (also in order to guarantee distance consistency)

Networks

The data locations are one for each vertex, plus a number of point proportional to length of the edge (roughly 10 observations for each unit of length).

We simulate data from the WM process with \(\alpha = 1\), \(\tau = 1\), \(\kappa = 1\). We do nsim=20 simulations, with fixed locations, and compute the median estimates across simulations for the \(\tau\) and \(\kappa\) parameters for both WM and isoCov models. When fitting WM, we fix \(\alpha\) to the true value of 1.

Fixed locations

Due to the unexpected asymmetry in the complete network, we consider another set of simulations where at each step we resample also the locations.

Averaged locations

Signal-based sensitivity

Here we investigate the sensitivity of sample-based estimates of some quantities of interest. An example borrowed from spatial statistics is the variogram \[ 2\gamma(h) = \frac{1}{\mid N_h \mid} \sum_{(i,j)\in N_h} (Z_i - Z_h)^2. \] As showed in Genton and Ruiz-Gazen (2010), this quantity can be written as a quadratic form \(Z^\intercal A Z\) of the data values \(Z=(Z_1,\dots,Z_N)^\intercal\), for a certain symmetric matrix \(A\). It follows that we have analytical expressions for the local and asymptotic influences (Genton and RUiz-Gazen, 2010): \[ \tau_i(\hat{\theta},Z) = 2a_i^\intercal Z, \] where \(a_i\) is the vector given by the i-th row of \(A\).

In the context of networks, a quantity of interest is the graph Laplacian. There are multiple definitions of graph Laplacian, but the basic one for an undirected graph is given by a \(n\times n\) matrix \(L\) with entries \[ L_{ij} = \begin{cases} d_i & \text{if} \quad i=j \\ -1 & \text{if} \quad (i,j)\in E \\ 0 & \text{otherwise} \end{cases}, \] where \(d_i\) is the degree of the node (number of edges associated to that node). In case of a weigthed graph with weight \(w_{ij}\) for the edge \((i,j)\in E\), one generalization is given by: \[ L_{ij} = \begin{cases} w_i & \text{if} \quad i=j \\ -w_{ij} & \text{if} \quad (i,j)\in E \\ 0 & \text{otherwise} \end{cases}, \] where \(w_i\) is the sum of the weights of the edges connected to node \(i\).

Considering a vertex-valued function \(Z:V\rightarrow \mathbb{R}\), there exists a measure of the weighted-smoothness given by the graph Laplacian quandratic form:

\[ S_2(Z) := \sum_{(i,j)\in E} w_{ij}(Z_j - Z_i)^2 = Z^\intercal L Z. \] This resembles to some extent the variogram definition. Note that here the squared difference are computed between all connected vertices rather than at a fixed lag \(h\). Moreover, the larger the weight, the more important is the difference. Therefore, in our context we may want to choose: \[ w_{ij} = 1/d_{\cdot \mathcal{G}}(i,j), \qquad \forall (i,j)\in E, \] with either the geodesic or resistance distance.

The advantage of \(S_2(Z)\) is that it is a quadratic form, and thus we can leverage Genton and Ruiz-Gazen (2010) and directly compute the local influence for each vertex: \[ \tau_i(S_2,Z) = 2l_i^\intercal Z, \] with \(l_i\) the i-th row of the graph Laplacian \(L\).

TODO We can consider extension of this idea to all observations on graph (maybe not trivial), and other version of the Laplacian (normalized, etc..).

Simulations

We do the following experiment:

1. We sample a network with a given node distribution.
2. We simulate on the vertexes from WM with \(\alpha=\kappa=\tau=1\).
3. We compute the local influence of each node for a total of nsim=100 simulations.

In particular, we sample a network with a power-law distribution for the node degree. That is, the degree distribution is \(\propto 1/x^a\). We set \(a=1\). We normalize all the edge lengths to be equal to 1, in order to isolate the effect of the node degree on the result.

Simulated network with power-law degree distribution

Boxplot of the node local influences on \(S_2(Z)\)

TODO Consider different topoligies and include branch lengths.

Definitions

1. Vertex closeness \[ c(v) = \frac{1}{\sum_{u\in V}d(u,v)} \]
2. Vertex betweenness \[ b(v) = \sum_{s\neq t \neq v \in V}\frac{\sigma(s,t\mid v)}{\sigma(s,t)}, \] where \(\sigma(s,t)\) is the total number of shortest paths from \(s\) to \(t\), and \(\sigma(s,t\mid v)\) is the number of those passing through \(v\).